#include "GRASP.h"
#include "Lista.h"
#include <sys/time.h>
#include <list>
#include <iostream>
#include <limits>


using namespace std;

SolucaoGRASPCobertura *GRASP::construcao(int clusterMin) {
    SolucaoGRASPCobertura *sol = new SolucaoGRASPCobertura();
    sol->init();
    //Inicializa a funcao gulosa adaptativa
    //Solucao::initGulosa();
    int pInit = 0;
    NoClu *cluster = Solucao::clusters.inicio;
    //Coloca na solucao as localizacoes que sao apenas Facilitadores.
    /*for(int i=0; i<Solucao::F; ++i){
            if(Solucao::type[i] == Solucao::FACILITY_ACTIVE){
                    sol->setElemento(i);
                    ++pInit;
                    if(pInit == Solucao::p)
                            break;
            }
    }*/
    bool impossible = false;
    while (pInit < Solucao::p) { //p-median
        //if((clusterMin > 0)&&(cluster->tamanho <= clusterMin))
        //	cluster = Solucao::clusters.inicio;
        cluster->candidatos = new Lista();

        //Inicializando a lista de candidatos
        ListaAtri *lista = cluster->lista;
        NoLista *a = lista->inicio;
        while (a) {
            if ((sol->solucao[a->elemento] != true) && (Solucao::type[a->elemento] != Solucao::CLIENT))
                cluster->candidatos->insereOrdenado(a->elemento, sol->g(a->elemento));
            a = a->proximo;
        }

        if (cluster->candidatos->count == 0) {
            if (impossible) {
                sol->avaliacao = 0;
                break;
            } else
                impossible = true;
            //Muda o cluster.
            cluster = cluster->proximo;
            if (cluster == NULL)
                cluster = Solucao::clusters.inicio;
            continue;
        }
        //Setando o valor de filtro dos elementos do LCR
        double gmax = cluster->candidatos->getPos(0)->gulosa;
        double gmin = cluster->candidatos->getPos(cluster->candidatos->count - 1)->gulosa;
        double filtro = gmax - this->alpha * (gmax - gmin);
        //printf("MIN: %f - MAX: %f FILTRO: %f\n", gmin, gmax, filtro);
        //Inicializando o LCR
        Lista LCR;
        for (int i = 0; i < cluster->candidatos->count; i++) {
            NoLista *aux = cluster->candidatos->getPos(i);
            //printf("GCAND[%d]: %f\n", aux->elemento, aux->gulosa);
            if ((aux->gulosa >= filtro) && (sol->solucao[aux->elemento] == false)) {
                LCR.insere(aux->elemento);
                //delete aux;
            } else {
                //delete aux;
                break;
            }
        }
        if (LCR.count == 0) {
            cluster = cluster->proximo;
            if (cluster == NULL)
                cluster = Solucao::clusters.inicio;
            continue;
        }
        //Escolha aleatoria do elemento na LCR
        NoLista *aux = LCR.getRandom();
        //printf("Pos: %d\n", aux->elemento);
        //Seta o elemento da solucao em sol
        sol->setElemento(aux->elemento);
        //printf("Construcao Parcial: %s\n", sol->print());
        //delete aux;
        ++pInit;

        //Percorrendo os outros clusters
        delete cluster->candidatos;
        cluster = cluster->proximo;
        if (cluster == NULL) {
            cluster = Solucao::clusters.inicio;
        }
    }
    /*if(impossible){
            puts("HERE!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!");
            return NULL;
	
    }*/
    //sol->f();
    /*printf("Construcao: %s\n", sol->print());
    printf("F: %d\n", sol->avaliacao);
    getchar();*/
    return sol;
}

SolucaoGRASPCobertura *GRASP::buscaLocal(SolucaoGRASPCobertura *solAtual) {
    //Criando os vizinhos da solucao atual
    SolucaoGRASPCobertura *sol = solAtual;
    SolucaoGRASPCobertura *solswap = sol->getVizinhosSWAP();
    if (solswap->avaliacao > sol->avaliacao) {
        delete sol;
        sol = solswap;
    } else {
        delete solswap;
    }

    return sol;
}

SolucaoGRASPCobertura *GRASP::svn(SolucaoGRASPCobertura *sol) {
    double fbl, aval;
    SolucaoGRASPCobertura *sbl = new SolucaoGRASPCobertura(sol);
    bool f = true;
    while (f) {
        f = false;

        do {
            fbl = sbl->avaliacao;
            sbl = this->buscaLocal(sbl);
            //if(fbl > sbl->avaliacao)
            //printf("BL CLU: %d\n", sbl->avaliacao);


        } while ((sbl->avaliacao - fbl) > 0.000001);
        //break;
        //do{
        SolucaoGRASPCobertura *sc = sbl;
        fbl = sc->avaliacao;
        sbl = sc->getVizinhosSWAPCluster();
        if ((sbl->avaliacao - fbl) > 0.000001) {
            //printf("CLUSTER BL: %d\n", sbl->avaliacao);
            f = true;
        }
        delete sc;

        //}while(fbl > sbl->avaliacao);
    }
    return sbl;
}

SolucaoGRASPCobertura *GRASP::perturbacao() {
    SolucaoGRASPCobertura *pert = NULL;

    int count[Solucao::F];
    for (int i = 0; i < Solucao::F; ++i)
        count[i] = 0;
    set<SolucaoGRASPCobertura *, SolucaoCompare>::iterator it = this->elite.begin();
    for (; it != this->elite.end(); ++it) {
        //(*it)->f();
        //cout << (*it)->print() << endl;
        //cout << (*it)->avaliacao << endl;
        SolucaoGRASPCobertura *sol = *it;
        for (int i = 0; i < Solucao::F; ++i) {
            if (sol->solucao[i] == true)
                ++count[i];
        }
    }

    //ns = elite->inicio;

    list<int> lout; //lista de concentradores que nunca estiveram na solucao
    list<int> lin; //lista de concentradores que sempre estiveram na solucao
    bool out[Solucao::F];
    bool out2[Solucao::F];
    for (int i = 0; i < Solucao::F; ++i) {
        out2[i] = false;
        if (count[i] == 0) {
            //if((rand() % 100) > 30){
            lout.push_back(i);
            out[i] = true;
            //}else
            //	out[i] = false;
        } else
            out[i] = false;
    }

    //bool mpiImprove;
    //do{
    //mpiImprove = false;
    double **M = new double*[Solucao::V];
    int numFacility = Solucao::F - lout.size();
    for (int i = 0; i < Solucao::F; ++i) {
        M[i] = new double[numFacility];
    }

    for (int j = 0, nj = 0; j < Solucao::F; ++j) {
        //bool find = false;
        //for(iter = candidatos.begin(); iter != candidatos.end(); ++iter){
        //      if(*iter == j){
        //              find = true;
        //              break;
        //      }

        //}
        if (count[j] == NUM_ITER)
            lin.push_back(nj);
        if (out[j])
            continue;
        //cout << "FAC: " << j << endl;
        for (int i = 0; i < Solucao::V; ++i) {
            M[i][nj] = Solucao::linkClient[i][j];
            //cout << M[i][nj] << " ";
        }
        //cout << endl;
        ++nj;
    }

    //for(int i=0; i < Solucao::tamanho; ++i){
    //      for(int j=0; j < numFacility; ++j){
    //              printf("M[%d][%d] : %f", i, j, M[i][j]);
    //      }
    //      printf("\n");
    //}exit(0);
    printf("FAC!=0: %d - FAC==1:%d\n", (int)numFacility, (int)lin.size());
    printf("ANTES OPT - F: %d\n", this->s->avaliacao);

    //SolucaoGRASPCobertura* OptimizeCplex(double **distancias, int *demanda, int V, int F, int P, float Dc, list<int> &lCon, bool *out, double fmeta);
    SolucaoGRASPCobertura * solOpt = Solucao::OptimizeCplex(M, Solucao::demanda, Solucao::V, numFacility, Solucao::p, (float) Solucao::D, lin, out, this->s->avaliacao, NULL);

    for (int i = 0; i < Solucao::F; ++i) {
        delete M[i];
    }
    delete M;

    if (solOpt->avaliacao > this->s->avaliacao) {
        //mpiImprove = true;
        this->s = solOpt;
        //elite->insert(solOpt);
    }

    printf("OPT: %s F: %d\n", solOpt->print(), solOpt->avaliacao);
    SolucaoGRASPCobertura *sbl = this->svn(solOpt);
    printf("BL: %s F: %d\n", sbl->print(), sbl->avaliacao);

    gettimeofday(&duracaoOtimizadorAntes, NULL);

    sbl = Solucao::OptimizeCplex(Solucao::linkClient, Solucao::demanda, Solucao::V, Solucao::F, Solucao::p, (float) Solucao::D, lin, out2, sbl->avaliacao, sbl);

    if (sbl->avaliacao > this->s->avaliacao) {
        //mpiImprove = true;
        this->s = sbl;
        //elite->insert(sbl);
    }

    gettimeofday(&duracaoOtimizadorDepois, NULL);

    /*if(mpiImprove){
            addFacilityIN(this->s, lout, out);
    }*/
    //}while(mpiImprove);
    //printf("COUNT: %d\n", c);

    //exit(0);

}

void GRASP::inicio(int GRASPmax) {
    gettimeofday(&tempoAntes, NULL);
    srand(time(NULL));
    Solucao::initCluster();
    //GRASPmax = 1;
    int finicial = 0;
    SolucaoGRASPCobertura *sol;
    for (int iter = 0; iter < GRASPmax; iter++) {
        int fConstrInicial = 0;
        printf("GRASP iteration %d\n ", (iter+1));
        //sol = this->construcao();
        sol = NULL;

        //Filtragem da construção (GRASP)
        for (int i = 0; i < FILTRO; i++) {
            SolucaoGRASPCobertura *sconstr = this->construcao(i % 3);
            if (sconstr == NULL)
                break;
            if (sconstr->avaliacao > fConstrInicial) {
                if (sol != NULL) {
                    delete sol;
                    //elite.insert(sol);
                }
                sol = sconstr;
                fConstrInicial = sconstr->avaliacao;
            } else
                //elite.insert(sconstr);
                delete sconstr;
        }
        if (sol == NULL)
            break;
        //elite->insert(new SolucaoGRASPCobertura(sol));
        //printf("Parcial: %s\n", sol->print());
        //SolucaoGRASPCobertura *sbl = new SolucaoGRASPCobertura(sol);

        //########## VNS###############/

        SolucaoGRASPCobertura *sbl;
        //if(iter % 2 == 0)
        sbl = this->svn(sol);
        //else
        //	sbl = sol;

        if (sbl->avaliacao < sol->avaliacao) {
            delete sbl;
            sbl = new SolucaoGRASPCobertura(sol);
        }
        //########## VNS###############/

        //printf("BUSCA: %s\n", sbl->print());
        //printf("F: %d\n", sbl->avaliacao);
        //getchar();

        if (sol != NULL)
            delete sol;

        if (sbl->avaliacao > finicial) {
            //printf("A: %d\n", sbl->avaliacao);
            //if(this->s != NULL)
            //	delete this->s;
            this->s = sbl;
            finicial = sbl->avaliacao;
            melhorIter = iter;
        }//else
        //delete sbl;
        //printf("INSERT: %d\n", sbl->avaliacao);
        elite.insert(sbl);
    }
    //elite.sort(SolucaoGRASPCobertura::compare);
    //this->perturbacao();

    gettimeofday(&tempoDepois, NULL);
}

void GRASP::start(int GRASPmax) {

    piorTodas = 99999999;
    melhorTodas = 0;

    for (int i = 0; i < numeroRepeticoes; i++) {

        printf("Start iteration %d\n", (i + 1));
        this->s = NULL;
        inicio(GRASPmax);

        if (s->avaliacao < piorTodas) {
            piorTodas = s->avaliacao;
        }

        if (s->avaliacao > melhorTodas) {
            melhorTodas = s->avaliacao;
        }

        timeval dif;
        timersub(&tempoDepois, &tempoAntes, &dif);
        long tempo;
        if (dif.tv_usec != 0)
            tempo = dif.tv_sec * 1000 + dif.tv_usec / 1000;
        else
            tempo = dif.tv_sec * 1000;

        mediaTodas += s->avaliacao;
        mediaTempo += tempo;

        printf("Resultado iteracao %d: %d - Tempo: %ld\n", (i+1), s->avaliacao, tempo);
    }

    mediaTodas /= numeroRepeticoes;
    mediaTempo /= numeroRepeticoes;
}


